package LC;

/**
 * https://leetcode.com/problems/house-robber/description/
 * You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed,
 * the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and
 * it will automatically contact the police if two adjacent houses were broken into on the same night.
 * Given a list of non-negative integers representing the amount of money of each house,
 * determine the maximum amount of money you can rob tonight without alerting the police.
 */
public class LC_198_HouseRobber_DP_Greedy {
    public static void main(String[] args) {
        System.out.println(Solution.rob(new int[]{1, 2, 3, 4, 1, 2, 3}));
    }

    static class Solution {
        static int rob(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
            int n = nums.length;
            int[] b = new int[n];
            int[] d = new int[n];
            b[0] = nums[0];
            d[0] = 0;
            for (int i = 1; i < n; i++) {
                b[i] = d[i - 1] + nums[i];
                d[i] = Math.max(b[i - 1], d[i - 1]);
            }
            return Math.max(d[n - 1], b[n - 1]);
        }
    }
}